//
// Created by yanhai on 2021/1/17.
//

#pragma once

#include <vector>
#include <list>
#include <map>
#include <string>

using std::vector;
using std::list;
using std::map;
using std::pair;
using std::string;

////////////////////////////////////////

// 概念，缩写
// 图：Graph
// 顶点：Vex（Vertex）
// 无向边：Edge
// 有向边（弧）：Arc
// 权：Weight
//

////////////////////////////////////////
typedef string VexType; // 顶点类型 用户定义
typedef int WeightType; // 权值类型 用户定义
#define INF 0x7F7F7F7F  // 顶点索引无效值

// 顶点类型
struct GVex {
    int idx;        // 顶点索引
    VexType data;   // 顶点信息
};

// 顶点集合类型
typedef vector<GVex> GraphVex;

// 边的表示方法 <'A', 'B'>
typedef pair<VexType, VexType> GArc;

// 边表节点
struct ArcNode {
    int idx;            // 顶点索引
    WeightType weight;  // 权

    bool operator==(const ArcNode &other) const
    {
//        return idx == other.idx && weight == other.weight;
        return idx == other.idx;
    }
};

// 边集合类型
typedef vector<list<ArcNode>> GraphArc;

// 遍历回调函数
typedef bool (*VisitFunc)(const GVex &vex);

class CGraph {
public:
    /**
     * 图对象
     * @param direct 是否是有向图
     */
    CGraph(bool direct = true) : _direct(direct) {}

    /**
     * 创建图
     * @param vex 顶点集合 'A'
     * @param arc 边集合 <'A', 'B'>
     * @param weights 权重集合
     */
    void CreateGraph(const vector<VexType> &vex,
                     const vector<GArc> &arc,
                     const vector<WeightType> &weights = vector<WeightType>());

    /**
     * 向图中添加顶点
     * @param v 顶点
     * @return true: 添加成功
     */
    bool InsertVex(const VexType &v);

    /**
     * 从图中删除顶点
     *
     * 除了删除顶点还需要删除相关的边信息
     * @param v 顶点
     * @return true: 成功
     */
    bool DeleteVex(const VexType &v);

    /**
     * 修改顶点信息
     * @param s 要修改的顶点
     * @param d 修改成什么
     * @return
     */
    bool UpdateVex(const VexType &s, const VexType &d);

    // 获取顶点（附加）信息

    // 判断顶点是否存在

    // 获取顶点的第一个邻接点

    // 获取顶点的下一个邻接点

    // 获取顶点的度（出度or入度）

    /**
     * 插入一条边信息
     * @param arc 边
     * @param weight 权重
     * @return
     */
    bool InsertArc(const GArc &arc, int weight = 0);

    /**
     * 从图中删除一条边
     * @param arc 边
     * @return true: 成功
     */
    bool DeleteArc(const GArc &arc);

    /**
     * 修改边的权
     * @param arc 要修改的边
     * @param weight 权
     * @return
     */
    bool UpdateArcWeight(const GArc &arc, const WeightType &weight);

    // 获取边信息（权）

    // 判断边是否存在

    /**
     * 获取顶点总数
     * @return
     */
    inline size_t VexSize() const
    {
        return _graph_vex.size();
    }

    /**
     * 对图进行深度优先遍历（不能遍历删除）
     * @param func
     */
    void DFSTraverse(VisitFunc func) const;

    /**
     * 对图进行广度优先遍历（不能遍历删除）
     * @param func
     */
    void BFSTraverse(VisitFunc func) const;

    /**
     * 迪杰斯特拉 最短路径
     * @param s 开始顶点
     * @param visited 是否被确认过
     * @param dis 距离s的距离
     * @param parent 距离s最短路径时的前一个顶点
     */
    void Dijkstra(const VexType &s,
                  vector<bool> &visited,
                  vector<WeightType> &dis,
                  vector<int> &parent) const;

    /**
     * 迪杰斯特拉 最短路径
     * @param s 开始顶点
     * @return 每个顶点的 <距离, 距离最近时的父顶点>
     */
    vector<pair<WeightType, int>> Dijkstra(const VexType &s) const;

    // 获取两顶点之间最短路径（并将详细的路径描述出来）
    list<VexType> VexPathMin(const VexType &from,
                             const VexType &to) const;

private:
    /**
     * 根据顶点信息查出对应的id
     * @param v 顶点
     * @return id
     */
    int _get_index(const VexType &v) const
    {
        auto it = _vex_idx.find(v);
        if (it == _vex_idx.end()) return -1;
        return it->second;
    }

    /**
     * 回溯 函数堆栈来实现，实际开发过程，图纵深 尾递归
     * 所有递归 都能转化为 递推
     * @param idx
     * @param visited
     * @param func
     */
    void _dfs_traverse(int idx, vector<bool> &visited, VisitFunc func) const;

    /**
     * 广度优先遍历
     * @param idx
     * @param visited
     * @param func
     */
    void _bfs_traverse(int idx, vector<bool> &visited, VisitFunc func) const;

private:
    GraphVex _graph_vex;        // 一维数组，存储顶点信息
    GraphArc _graph_arc;        // 邻接表（边表/弧尾的出边表），存储边信息

    map<VexType, int> _vex_idx; // 顶点信息 和 存储顶点信息的一维数组 的映射关系
    bool _direct;               // 是否是有向图
};
